//
// Created by user on 2022/2/16.
//
/*
 * 三路快排
 */
#include <iostream>
#include <vector>
using namespace std;
void threeQuickSort(vector<int>&nums, int lo, int hi);

void threeQuickSort(vector<int>&nums, int lo, int hi){
    if (lo>=hi){
        return;
    }
    int index = rand()%(hi-lo+1)+lo;
    swap(nums[index], nums[hi]);
    int pivot = nums[hi];


    int less = lo;
    int great = hi;
    int i = lo;
    //排序
    while (i<=great){
        if(nums[i]<pivot){
            swap(nums[i], nums[less]);
            less++;
            i++;
        }else if(nums[i]>pivot){
            swap(nums[i], nums[great]);
            great--;
        }else{
            i++;
        }
    }
    threeQuickSort(nums, lo, less-1);
    threeQuickSort(nums, great+1, hi);

}